<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>busketSort</title>
</head>

<body>
    <script>
        function insertSort(arr) {
            for (let i = 1; i < arr.length; i++) {
                let temp = arr[i]
                let j = i - 1
                while (j >= 0 && arr[j] > temp) {
                    arr[j + 1] = arr[j]
                    j--
                }
                arr[j + 1] = temp
            }
            return arr
        }

        function busketSort(arr, bucketSize) {
            if (arr.length == 0) return arr;
            let i = 0
            let minValue = Math.min(...arr)
            let maxValue = Math.max(...arr)
            let DEFAULT_BUCKET_SIZE = 5
            bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
            //设置桶的大小，这桶的映射函数有关
            let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
            let buckets = new Array(bucketCount)
            //初始化桶
            for (; i < buckets.length; i++) {
                buckets[i] = []
            }
            //通过映射函数，将arr中的每个数分配到对应的桶中
            for (i = 0; i < arr.length; i++) {
                buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i])
            }
            //将arr清空
            arr.length = 0
            for (i = 0; i < buckets.length; i++) {
                //对每个桶的元素进行排序
                buckets[i] = insertSort(buckets[i])
                for (let j = 0; j < buckets[i].length; j++) {
                    arr.push(buckets[i][j])
                }
            }
            return arr //[].concat(...buckets)
        }
        console.log(busketSort([9, 5, 4, 11, 8, 1, 3]))
    </script>
</body>

</html>